package com.fulu.javabase.arithmetic.array;

import java.util.Arrays;

/**
 * Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
 *
 * https://leetcode.cn/problems/squares-of-a-sorted-array/
 */
public class SquaresofaSortedArray {
    /**
     * 时间复杂度 O(nlogn)
     * 空间复杂度 O(nlogn)
     * @param nums
     * @return
     */
    public static int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i] * nums[i];
            for (int j = 0; j <= i; j++) {
                if(result[j] > result[i]){
                    int tmp = result[j];
                    result[j] = result[i];
                    result[i] = tmp;
                }
            }

        }
        return result;
    }

    /**
     * 双指针法
     * 时间 O(n)
     * 空间 O(n)
     * @param nums
     * @return
     */
    public static int[] sortedSquares1(int[] nums) {
        int prep = 0;
        int rear = nums.length - 1;
        int[] result = new int[nums.length];
        int i = nums.length - 1;
        while(prep <= rear){
            if(nums[prep] * nums[prep] > nums[rear] * nums[rear]){
                result[i] = nums[prep] * nums[prep];
                prep++;
            }else{
                result[i] = nums[rear] * nums[rear];
                rear--;
            }
            i--;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-4,-1,0,3,10};
        System.out.println(Arrays.toString(sortedSquares1(nums)));
    }
}
